package gaileenchess;

import java.util.LinkedList;
import java.util.Comparator;
import java.util.ListIterator;
import java.util.Collections;

public class History
{
    /*private LinkedList< int[] > p;
    private LinkedList< LinkedList<Board.Position.Move> > wm;
    private LinkedList< LinkedList<Board.Position.Move> > bm;*/
    private LinkedList< Data > data;
    
    private static DataComparator cmp = new DataComparator();
    private static MoveComparator mcmp = new MoveComparator();
    
    
    public History()
    {
        reset();
    }
    
    public void reset()
    {
        /*this.p = new LinkedList< int[] >();
        this.wm = new LinkedList< LinkedList<Board.Position.Move> >();
        this.bm = new LinkedList< LinkedList<Board.Position.Move> >();*/
        this.data = new LinkedList< Data >();
    }
    
    private int[] boardHash(Piece[][] p)
    {
        // we represent each (of 64) square on the board in 4 bits (enough to account for 6 piece types (with colour) plus empty)
        //   giving 256 bits = 32 bytes = 8 ints required
        int[] ret = new int[8];
        
        int i = 0;
        int shift = 7;
        
        for(int x = 0; x < 8; x++)
        {
            for(int y = 0; y < 8; y++)
            {
                int data = -1;
                Piece piece = p[x][y];
                
                if(piece != null)
                {
                    data = (piece.getSide().ordinal() << 3) | piece.getType().ordinal();
                }
                
                if(shift < 0)
                {
                    shift = 7;
                    i++;
                    ret[i] = 0;
                }
                
                ret[i] |= (data & 0x0000000f) << (4 * shift);
                
                shift--;
            }
        }
        
        return ret;
    }
    
    // NOTE: this function assumes the lists are sorted
    private LinkedList<Integer> movesHash(LinkedList<Board.Position.Move> moves)
    {
        //6 bits/pos = 12 bits/move = 2 moves/int, 8 wasted bits/int = 4 wasted bits/move => essentially 16 bits/move
        LinkedList<Integer> ret = new LinkedList<Integer>();
        int shift = 1;
        int data = 0;
        for(Board.Position.Move m : moves)
        {
            //can make numbers between 0-77, ie up to 7 bits
            int tempdata = ((m.p.row * 10 + m.p.column) << 8) | (m.q.row * 10 + m.q.column);
            
            if(shift < 0)
            {
                ret.addFirst(data);
                data = 0;
                shift = 1;
            }
            
            data |= (tempdata & 0x0000ffff) << (16 * shift);
            
            shift--;
        }
        
        if(shift < 0)
        {
            ret.addFirst(data);
        }
        
        return ret;
    }
    
    private int addSort(LinkedList< Data > list, Data data, Comparator<Data> comp)
    {
        ListIterator<Data> it = list.listIterator(0);
        
        while(it.hasNext())
        {
            Data current = it.next();
            int result = comp.compare(current, data);
            
            if(result == 0)
            {
                // this means an instance of data is already in the list, just add to the instance count and return
                //   (ie, discard new data object)
                
                return ++current.instances; // (increment then return)
            }
            else if(result == -1)
            {
                // this means we're too far in the list, we must backtrack if possible
                //   data becomes the only instance (if we're too far, we know there isn't
                //   another instance in the list or we'd have already found it and stopped)
                data.instances = 1;
                
                if(it.hasPrevious())
                {
                    // if we're here, it is possible to simply backtrack, so do so and add the data to the list here
                    current = it.previous();
                    it.add(data);
                }
                else
                {
                    // here it is not possible to backtrack, which means we need to add data to the beginning of the list
                    data.instances = 1;
                    list.addFirst(data);
                }
                
                return 1;
            }
        }
        
        // if we get here, it means the new element is larger than all the others, so it should be
        //   placed at the end of the list, and it becomes the only instance
        data.instances = 1;
        list.addLast(data);
        return 1;
    }
    
    public int add(Board board, Player[] players)
    {
        int[] b = boardHash(board.getPos());
        LinkedList<Board.Position.Move> vm1 = players[0].getValidMoves(false, 0);
        LinkedList<Board.Position.Move> vm2 = players[1].getValidMoves(false, 1);
        Collections.sort(vm1, mcmp);
        Collections.sort(vm2, mcmp);
        LinkedList<Integer> m1 = movesHash(vm1);
        LinkedList<Integer> m2 = movesHash(vm2);
        Data d = new Data(b, m1, m2);
        
        return addSort(this.data, d, this.cmp);
    }
    
    private class Data
    {
        public int[] p;
        public LinkedList<Integer> wm;
        public LinkedList<Integer> bm;
        
        public int instances;
        
        
        Data(int[] p, LinkedList<Integer> wm, LinkedList<Integer> bm)
        {
            this.p = p;
            this.wm = wm;
            this.bm = bm;
            instances = 1;
        }
    }
    
    private static class MoveComparator implements Comparator< Board.Position.Move >
    {
        public int compare(Board.Position.Move m1, Board.Position.Move m2)
        {
            if(m1.p.row == m2.p.row)
            {
                if(m1.p.column == m2.p.column)
                {
                    return 0;
                }
                else if(m1.p.column > m2.p.column)
                {
                    return 1;
                }
                
                return -1;
            }
            else if(m1.p.row > m2.p.row)
            {
                return 1;
            }
            
            return -1;
        }
    }
    
    private static class DataComparator implements Comparator< Data >
    {
        private int compareInt(int i1, int i2)
        {
            if(i1 > i2)
            {
                return 1;
            }
            else if(i1 < i2)
            {
                return -1;
            }
            
            return 0;
        }
        
        private int compareIntArr(int[] p1, int[] p2)
        {
            for(int x = 0; x < 8; x++)
            {
                int result = compareInt(p1[x], p2[x]);
                
                if(result != 0)
                {
                    return result;
                }
            }
            
            return 0;
        }
        
        private int compareIntList(LinkedList<Integer> m1, LinkedList<Integer> m2)
        {
            int len1 = m1.size();
            int len2 = m2.size();
            
            if(len1 > len2)
            {
                return 1;
            }
            else if(len1 < len2)
            {
                return -1;
            }
            
            ListIterator<Integer> itr = m2.listIterator(0);
            for(Integer p1 : m1)
            {
                int m1i = p1.intValue();
                int m2i = itr.next().intValue();
                int result = compareInt(m1i, m2i);
                
                if(result != 0)
                {
                    return result;
                }
            }
            
            return 0;
        }
        
        public int compare(Data d1, Data d2)
        {
            int result = compareIntArr(d1.p, d2.p);
            
            if(result == 0)
            {
                result = compareIntList(d1.wm, d2.wm);
                
                if(result == 0)
                {
                    result = compareIntList(d1.bm, d2.bm);
                }
            }
            
            return result;
        }
    }
}
